home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / fax / src / util / Dictionary.c++ < prev    next >
C/C++ Source or Header  |  1994-08-01  |  8KB  |  338 lines
  1. /*    $Header: /usr/people/sam/fax/util/RCS/Dictionary.c++,v 1.8 1994/02/28 14:24:09 sam Rel $ */
  2. /*
  3.  * Copyright (c) 1990, 1991, 1992, 1993, 1994 Sam Leffler
  4.  * Copyright (c) 1991, 1992, 1993, 1994 Silicon Graphics, Inc.
  5.  *
  6.  * Permission to use, copy, modify, distribute, and sell this software and 
  7.  * its documentation for any purpose is hereby granted without fee, provided
  8.  * that (i) the above copyright notices and this permission notice appear in
  9.  * all copies of the software and related documentation, and (ii) the names of
  10.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  11.  * publicity relating to the software without the specific, prior written
  12.  * permission of Sam Leffler and Silicon Graphics.
  13.  * 
  14.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  15.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  16.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  17.  * 
  18.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  19.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  20.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  21.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  22.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  23.  * OF THIS SOFTWARE.
  24.  */
  25. #include "Dictionary.h"
  26.  
  27. #define DEFAULTSIZE 31
  28.  
  29. fxIMPLEMENT_PtrArray(fxDictBuckets,fxDictBucket *);
  30. fxIMPLEMENT_PtrArray(fxDictIters, fxDictIter *);
  31.  
  32. #define KEYAT(base) (base)
  33. #define    VALUEAT(base) (void*)(((char*)base) + keysize)
  34.  
  35. #define KEY(b) KEYAT((b)->kvmem)
  36. #define VALUE(b) VALUEAT((b)->kvmem)
  37.  
  38. fxDictionary::fxDictionary(u_int ksize, u_int vsize,u_int initsize)
  39. {
  40.     if (initsize == 0) initsize = DEFAULTSIZE;
  41.     buckets.resize(initsize);
  42.     keysize = ksize;
  43.     valuesize = vsize;
  44.     numItems = 0;
  45. }
  46.  
  47. fxDictionary::fxDictionary(const fxDictionary &a)
  48. {
  49.     for (int i = 0; i < a.buckets.length(); i++) {
  50.     fxDictBucket * sb = a.buckets[i];
  51.     while (sb) {
  52.         addInternal(KEY(sb),VALUE(sb));
  53.         sb = sb->next;
  54.     }
  55.     }
  56. }
  57.  
  58. fxDictionary::~fxDictionary()
  59. {
  60. }
  61.  
  62. void fxDictionary::cleanup()
  63. {
  64.     u_int l = buckets.length();
  65.     for (u_int i=0; i < l; i++) {
  66.     fxDictBucket * bucket = buckets[i];
  67.     while (bucket) {
  68.         fxDictBucket * bucket2 = bucket->next;
  69.         destroyKey(KEY(bucket));
  70.         destroyValue(VALUE(bucket));
  71.         delete bucket;
  72.         bucket = bucket2;
  73.     }
  74.     buckets[i] = 0;
  75.     }
  76.     l = iters.length();
  77.     for (i=0; i < l; i++) {
  78.     iters[i]->dict = 0;
  79.     iters[i]->node = 0;
  80.     iters[i]->invalid = TRUE;
  81.     }
  82. }
  83.  
  84. fxDictBucket::~fxDictBucket()
  85. {
  86.     delete kvmem;
  87. }
  88.  
  89. void
  90. fxDictionary::operator=(const fxDictionary &a)
  91. {
  92.     assert(keysize == a.getKeySize());
  93.     assert(valuesize == a.getValueSize());
  94.     if (this == &a) return;
  95. #ifdef __GNUC__
  96.     cleanup();
  97. #else
  98.     fxDictionary::~fxDictionary();
  99. #endif
  100.     for (int i = 0; i < a.buckets.length(); i++) {
  101.     fxDictBucket * db = a.buckets[i];
  102.     while (db) {
  103.         addInternal(KEY(db), VALUE(db));
  104.         db = db->next;
  105.     }
  106.     }
  107. }
  108.  
  109. void
  110. fxDictionary::addInternal(const void* key, const void* value)
  111. {
  112.     u_int index = (u_int)(hashKey(key) % buckets.length());
  113.     fxDictBucket * bucket = buckets[index];
  114.     while (bucket && compareKeys(key,KEY(bucket))) {
  115.     bucket = bucket->next;
  116.     }
  117.     if (bucket) {     // just change the value
  118.     destroyValue(VALUE(bucket));
  119.     copyValue(value,VALUE(bucket));
  120.     return;
  121.     } else {
  122.     void * kvmem = malloc(keysize + valuesize);
  123.     copyKey(key,KEYAT(kvmem));
  124.     copyValue(value,VALUEAT(kvmem));
  125.     fxDictBucket * newbucket = new fxDictBucket(kvmem,buckets[index]);
  126.     buckets[index] = newbucket;
  127.     numItems++;
  128.     }
  129. }
  130.  
  131. void*
  132. fxDictionary::find(const void* key, void **keyp) const
  133. {
  134.     u_int index = (u_int)(hashKey(key) % buckets.length());
  135.     fxDictBucket * bucket = buckets[index];
  136.     while (bucket && compareKeys(key,KEY(bucket))) bucket = bucket->next;
  137.     if (bucket) {
  138.     if (keyp != 0) *keyp = &KEY(bucket);
  139.     return VALUE(bucket);
  140.     } else {
  141.     if (keyp != 0) *keyp = 0;
  142.     return 0;
  143.     }
  144. }
  145.  
  146. void*
  147. fxDictionary::findCreate(const void* key)
  148. {
  149.     u_int index = (u_int)(hashKey(key) % buckets.length());
  150.     fxDictBucket * bucket = buckets[index];
  151.     while (bucket && compareKeys(key,KEY(bucket))) bucket = bucket->next;
  152.     if (bucket)
  153.     return VALUE(bucket);
  154.     else {
  155.     char * kvmem = (char *)malloc(keysize + valuesize);
  156.     copyKey(key,KEYAT(kvmem));
  157.     createValue(VALUEAT(kvmem));
  158.     fxDictBucket * bucket = new fxDictBucket(kvmem,buckets[index]);
  159.     buckets[index] = bucket;
  160.     numItems++;
  161.     return VALUEAT(kvmem);
  162.     }
  163. }
  164.  
  165. void
  166. fxDictionary::remove(void const* key)
  167. {
  168.     u_int index = (u_int)(hashKey(key) % buckets.length());
  169.     fxDictBucket * bucket = buckets[index];
  170.     fxDictBucket ** prev = &buckets[index];
  171.     while (bucket && compareKeys(key,KEY(bucket))) {
  172.     prev = &bucket->next;
  173.     bucket = bucket->next;
  174.     }
  175.     if (bucket) {
  176.     *prev = bucket->next;
  177.     destroyKey(KEY(bucket));
  178.     destroyValue(VALUE(bucket));
  179.     invalidateIters(bucket);
  180.     delete bucket;
  181.     numItems--;
  182.     }
  183. }
  184.  
  185. void *
  186. fxDictionary::cut(void const* key)
  187. {
  188.     u_int index = (u_int)(hashKey(key) % buckets.length());
  189.     fxDictBucket * bucket = buckets[index];
  190.     fxDictBucket ** prev = &buckets[index];
  191.     while (bucket && compareKeys(key,KEY(bucket))) {
  192.     prev = &bucket->next;
  193.     bucket = bucket->next;
  194.     }
  195.     if (bucket) {
  196.     *prev = bucket->next;
  197.     void * v = malloc(valuesize);
  198.     memcpy(v,VALUE(bucket),valuesize);
  199.     destroyKey(KEY(bucket));
  200.     // no need to destroy value because it has moved to *v
  201.     invalidateIters(bucket);
  202.     delete bucket;
  203.     numItems--;
  204.     return v;
  205.     } else {
  206.     return 0;
  207.     }
  208. }
  209.  
  210. u_long
  211. fxDictionary::hashKey(void const *key) const
  212. {
  213.     u_long u = 0;
  214.     u_long const * p = (u_long const *)key;
  215.     int l = (int)keysize;
  216.     while (l>=sizeof(u_long)) {
  217.     u ^= *p++;
  218.     l -= sizeof(u_long);
  219.     }
  220.     return u;
  221. }
  222.  
  223. void fxDictionary::destroyKey(void *) const { }
  224. void fxDictionary::destroyValue(void *) const { }
  225.  
  226. void
  227. fxDictionary::addIter(fxDictIter *i)
  228. {
  229.     iters.append(i);
  230. }
  231.  
  232. void
  233. fxDictionary::removeIter(fxDictIter *i)
  234. {
  235.     iters.remove(iters.find(i));
  236. }
  237.  
  238. void
  239. fxDictionary::invalidateIters(const fxDictBucket *db) const
  240. {
  241.     u_int l = iters.length();
  242.     for (u_int i = 0; i<l; i++) {
  243.     fxDictIter * di = iters[i];
  244.     if (di->node == db) {
  245.         (*di)++;
  246.         if (di->dict) di->invalid = TRUE;
  247.     }
  248.     }
  249. }
  250.  
  251. //----------------------------------------------------------------------
  252.  
  253. fxDictIter::fxDictIter()
  254. {
  255.     invalid = FALSE;
  256.     dict = 0;
  257.     bucket = 0;
  258.     node = 0;
  259. }
  260.  
  261. fxDictIter::fxDictIter(fxDictionary& d)
  262. {
  263.     invalid = FALSE;
  264.     dict = &d;
  265.     bucket = 0;
  266.     node = d.buckets[bucket];
  267.     d.addIter(this);
  268.     if (!node) advanceToValid();
  269. }
  270.  
  271. fxDictIter::~fxDictIter()
  272. {
  273.     if (dict) dict->removeIter(this);
  274. }
  275.  
  276. void
  277. fxDictIter::operator=(fxDictionary& d)
  278. {
  279.     if (dict) dict->removeIter(this);
  280.     dict = &d;
  281.     bucket = 0;
  282.     node = d.buckets[bucket];
  283.     invalid = FALSE;
  284.     d.addIter(this);
  285.     if (!node) advanceToValid();
  286. }
  287.  
  288. void *
  289. fxDictIter::getKey() const
  290. {
  291.     if (invalid) return 0;
  292.     else return KEY(node);
  293. }
  294.  
  295. void *
  296. fxDictIter::getValue() const
  297. {
  298.     if (invalid) return 0;
  299.     else return (char *)node->kvmem + dict->keysize;
  300. }
  301.  
  302. void
  303. fxDictIter::increment()
  304. {
  305.     if (!dict) return;
  306.     if (invalid) {
  307.     invalid = FALSE;
  308.     return;
  309.     }
  310.     node = node->next;
  311.     if (node) return;
  312.  
  313.     // otherwise, find another node!
  314.     advanceToValid();
  315. }
  316.  
  317. void
  318. fxDictIter::advanceToValid()
  319. {
  320.     u_int len = dict->buckets.length();
  321.     fxDictBucket * n;
  322.     for(;;) {
  323.     bucket++;
  324.     assert(bucket<=len);
  325.     if (bucket == len) {
  326.         dict->removeIter(this); // it's done with us
  327.         dict = 0;
  328.         invalid = TRUE;
  329.         break;
  330.     }
  331.     if (n = dict->buckets[bucket]) { // intentional =
  332.         node = n;
  333.         invalid = FALSE;
  334.         break;
  335.     }
  336.     }
  337. }
  338.